package de.tum.wi.som.rcpsp.business.impl;

public class SumOfSubset {
	

	// Recursive method that returns true iff a subset of values in
	// numbers[0..size-1] sums to target.	
	public static boolean subsetsumrec(int[] numbers, int target, int size) {
		
		// Nothing sums to 0.
		if (target == 0)
			return true;
			
		// Can't some to anything else without some numbers.
		if (size == 0)
			return false;
			
		// Either we don't take the number stored at index size-1...or we do.
		return subsetsumrec(numbers, target, size-1) ||
			   subsetsumrec(numbers, target-numbers[size-1], size-1);
	}
	
	// Returns true iff numbers has a subset of values that adds upto target.
	public static boolean subsetsum(int[] numbers, int target) {
		
		
		boolean[] answers = new boolean[target+1];
		answers[0] = true;
		for (int i=1; i<answers.length; i++)
			answers[i] = false;
			
		// Consider each item one by one.
		for (int i=0; i<numbers.length; i++) {
		
			// Loop through the array backwards, since we don't want to add in
			// a single element twice.
			for (int sum=target; sum >= numbers[i]; sum--) {
				
				// If we have a way to add to sum-numbers[i], now with numbers[i]
				// we can add to sum...
				if (answers[sum-numbers[i]])
					answers[sum] = true;
			}	
			
		}
		return answers[target];
	}
}